package dp;

import org.junit.Test;

public class LongestPalindromeSubseq516 {

    @Test
    public void test() {
        longestPalindromeSubseq("bbbab");
        longestPalindromeSubseq("cbbd");
        longestPalindromeSubseq("a");
        longestPalindromeSubseq("ac");
        longestPalindromeSubseq("bb");
    }

    public int longestPalindromeSubseq(String s) {
        // 注意, 不需要这个maxLen, 因为 maxLen = dp[0][s.length()-1]
        // int maxLen = 1;

        int[][] dp = new int[s.length()][s.length()];

        for (int k = 1; k <= s.length(); k++) {
            for (int i = 0; i <= s.length() - k; i++) {
                dp[i][i+k-1] = 1;
                if (s.charAt(i) == s.charAt(i+k-1)) {
                    if (k <= 2) {
                        // 注意: 这里不要continue, 否则没法更新maxLen
                        dp[i][i+k-1] = k;
                    } else {
                        dp[i][i+k-1] = dp[i+1][i+k-2] + 2;
                    }
                }
                if (k > 2) {
                    dp[i][i + k - 1] = Math.max(dp[i][i + k - 1], dp[i][i + k - 2]);
                    dp[i][i + k - 1] = Math.max(dp[i][i + k - 1], dp[i + 1][i + k - 1]);
                }
            }
        }
        System.out.format("s: %s, maxLen: %s\n", s, dp[0][s.length()-1]);
        return dp[0][s.length()-1];
    }
}
